import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LCP128 {
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        int[] nums1 = {0,3,7,2,5,8,4,6,0,1};
        System.out.println(longestConsecutive(nums));
        System.out.println(longestConsecutive(nums1));
    }

    /**
     给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。-10^9 <= nums[i] <= 10^9   时间复杂度为O(n)
     遍历，有序、不重复   什么数据结构来存：一个数组 表明对应元素是否存在，连续的一段一直加1
     出错情况 [0,-1]
     **/
    public static int longestConsecutive1(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);

        int[] flagArray = new int[100000];
        for (int num : nums) {
            flagArray[num] = 1;   //如果超过10000怎么办，扩容？
        }

        int length = 0;
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < flagArray.length; i++) {  //0 1 1 1 0 1 1 0 0 1 0
            if (i==0 && flagArray[i] == 1 || flagArray[i] == 1 && flagArray[i-1] == 0) {  //注意 i=0 的情况
                startIndex = i;  //1
            } else if ((i == flagArray.length -1 && flagArray[i] == 1) || flagArray[i] == 1 && flagArray[i+1] == 0){  //注意最后一个元素
                endIndex = i;
            }
            if (endIndex - startIndex + 1> length) {
                length = endIndex - startIndex + 1;
            }

        }
        return length;
    }

    /**
     * 用哈希表存放数组中的树 Map<Key,Value>
     */
    public static int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<>();
        for (int num : nums) {
            num_set.add(num);
        }
        int longestStreak = 0;
        for (Integer num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

}
